#define _CRT_SECURE_NO_WARNINGS 1

#include "Stack.h"

void StackInit(Stack* ps)//初始化
{
	assert(ps);
	ps->array = NULL;
	ps->top = 0;  // ps->top = -1
	ps->capacity = 0;
}

void StackDestroy(Stack* ps)//销毁
{
	assert(ps);

	free(ps->array);
	ps->array = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps, StackDataType x)//进栈
{
	assert(ps);
	if (ps->top == ps->capacity) 
	{
		int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        StackDataType* tmp_arr =(StackDataType *) realloc(ps->array, sizeof(StackDataType) * new_capacity);
		if (tmp_arr == NULL) 
		{
			printf("realloc failed!\n");
			exit(-1);
		}
		// 更新
		ps->array = tmp_arr;
		ps->capacity = new_capacity;
	}

	ps->array[ps->top] = x;// 填入数据
	ps->top++;
}

bool StackEmpty(Stack* ps)//判断栈是否为空
{
	assert(ps);

	return ps->top == 0; //等于0就是空，就是真
}

void StackPop(Stack* ps)// 出栈
{
	assert(ps);
	//assert(ps->top > 0);  //防止top为空
	assert(!StackEmpty(ps));

	ps->top--;//--不让访问数组最后一个元素就行
}

StackDataType StackTop(Stack* ps)//返回栈顶数据
{
	assert(ps);
	//assert(ps->top > 0);  //防止top为空
	assert(!StackEmpty(ps));

	return ps->array[ps->top - 1];
}

int StackSize(Stack* ps) //计算栈的大小
{
	assert(ps);

	return ps->top;// 因为我们设定top是指向栈顶的下一个，所以top就是size
}

int stackfull(Stack* st)//(3) 判断栈满
{
	assert(st);

	return st->top == st->capacity;
}

void display(Stack* st)//(5) 遍历顺序栈
{
	assert(st);

	for (int i = 0;i < st->top;i++)
	{
		printf("%d ", st->array[i]);
	}
	printf("\n");
}

int decimal_to_octal(int n)
{
	//十进制整数转换成八进制
	Stack s;
	StackInit(&s);
	while (n)
	{
		StackPush(&s, n % 8);
		n /= 8;
	}
	int res = 0;
	while (!StackEmpty(&s))
	{
		//printf("%d", StackTop(&s));
		res = res * 10 + StackTop(&s);
		StackPop(&s);
	}
	//printf("\n");
	StackDestroy(&s);

	return res;
}

//力扣：20.有效的括号
//难度简单
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//有效字符串需满足：
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//每个右括号都有一个对应的相同类型的左括号。
//示例 2：
//输入：s = "()[]{}"
//输出：true
//示例 3：
//输入：s = "(]"
//输出：false
//提示：
//1 <= s.length <= 104
//s 仅由括号 '()[]{}' 组成
//bool isValid(char* s) {
//
//}
//解析代码：
//这道题用C++写就很简单，用C语言写就需要创建一个栈。（可以用数组什么的，但不好）
//我们刚写了一个栈，直接把Stack.h和Stack.c复制粘贴过去, 把头文件删掉，
//再把typedef int StackDataType; 改成typedef char StackDataType;
//bool isValid(char* s) {
//	Stack st;
//	StackInit(&st);
//	while (*s)
//	{
//		if ((*s == '(') || (*s == '[') || (*s == '{'))
//		{
//			StackPush(&st, *s);
//		}
//		else
//		{
//			//栈是空，且遇到右括号了，栈里面没有左括号
//			if (StackEmpty(&st))
//			{
//				StackDestroy(&st);
//				return false;
//			}
//
//			StackDataType top = StackTop(&st);
//			StackPop(&st);
//
//			if ((top == '(' && *s != ')')
//				|| (top == '[' && *s != ']')
//				|| (top == '{' && *s != '}'))
//			{
//				StackDestroy(&st);
//				return false;
//			}
//		}
//		s++;
//	}
//	//如果栈不是空，说明还有左括号没出完，不合题意
//	//此时StackEmpty返回false，相反，栈是空，返回true
//	bool ret = StackEmpty(&st);
//	StackDestroy(&st);
//	return ret;
//}
//
////力扣：232.用栈实现队列
////难度简单
////请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作
////（push、pop、peek、empty）：
////实现 MyQueue 类：
////? void push(int x) 将元素 x 推到队列的末尾
////? int pop() 从队列的开头移除并返回元素
////? int peek() 返回队列开头的元素
////? boolean empty() 如果队列为空，返回 true ；否则，返回 false
//typedef struct {
//	Stack pushST;
//	Stack popST;
//} MyQueue;
//
//
//MyQueue* myQueueCreate() {
//	MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
//	StackInit(&q->pushST);
//	StackInit(&q->popST);
//
//	return q;
//}
//
//void myQueuePush(MyQueue* obj, int x) {
//	StackPush(&obj->pushST, x);
//}
//
//int myQueuePop(MyQueue* obj) {
//	//int pop() 从队列的开头移除并返回元素
//	//如果popST中没有数据，就把pushST的数据拿过去
//	//这样popST的数据就符合先进先出了
//	if (StackEmpty(&obj->popST))
//	{
//		while (!StackEmpty(&obj->pushST))
//		{
//			StackPush(&obj->popST, StackTop(&obj->pushST));
//			StackPop(&obj->pushST);
//		}
//	}
//	//有数据就直接出（删后返回）
//	int ret = StackTop(&obj->popST);
//	StackPop(&obj->popST);
//	return ret;
//}
//
//int myQueuePeek(MyQueue* obj) {
//	//int peek() 返回队列开头的元素
//	//如果popST中没有数据，就把pushST的数据拿过去
//	if (StackEmpty(&obj->popST))
//	{
//		while (!StackEmpty(&obj->pushST))
//		{
//			StackPush(&obj->popST, StackTop(&obj->pushST));
//			StackPop(&obj->pushST);
//		}
//	}
//	return StackTop(&obj->popST);//不删，直接取
//}
//
//bool myQueueEmpty(MyQueue* obj) 
//{
//	return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
//}
//
//void myQueueFree(MyQueue* obj) {
//	StackDestroy(&obj->pushST);
//	StackDestroy(&obj->popST);
//	free(obj);
//}